There Is No Preview Available For This Item
This item does not appear to have any files that can be experienced on Archive.org.
Please download files in this item to interact with them on your computer.
Show all files
We discuss several fascinating concepts and algorithms in graph theory that arose in the design of a nearly-linear time algorithm for solving diagonally-dominant linear systems. We begin by defining a new notion of what it means to approximate a graph by another graph, and explain why these sparse approximations enable the fast solution of linear equations. To build these sparsifiers, we rely on low-stretch spanning trees, random matrix theory, spectral graph theory, and graph partitioning algorithms.
The need to quickly partition a graph leads us to the local clustering problem: given a vertex in a massive graph, output a small cluster near that vertex in time proportional to the size of the cluster.
We use all these tools to design nearly-linear time algorithms for solving diagonally-dominant systems of linear equations, and give some applications.
This talk focuses on joint work with Shang-Hua Teng, and touches on work by Vaidya, Gremban, Miller, Koutis, Emek, Elkin, Andersen, Chung, Lang, Daitch, Srivastava and Batson.